package leetcode;


import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉搜索树
 */
public class l0098_验证二叉搜索树_层序遍历_需要默写出来 {

    private Queue<TreeNode> nodes = new LinkedList<>();
    private Queue<Integer> mins = new LinkedList<>();
    private Queue<Integer> maxes = new LinkedList<>();

    private void offer(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return;
        }
        nodes.offer(node);
        mins.offer(min);
        maxes.offer(max);
    }

    public boolean isValidBST(TreeNode root) {
        //前置校验
        if (root == null) {
            return true;
        }

        offer(root, null, null);
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();
            Integer min = mins.poll();
            Integer max = maxes.poll();
            if (min != null && node.val <= min) {
                return false;
            }
            if (max != null && node.val >= max) {
                return false;
            }
            offer(node.left, min, node.val);
            offer(node.right, node.val, max);
        }
        return true;
    }

}
